模拟赛题解/2025.10.13 模拟赛

T1-接雨滴（glory）

题面

Moon 发现自己来到了一个二维平面上，但是自己只能在 $y=0$ 的直线上以不超过 $v_cm/s$ 的速度行走（可以折返来回行走）。这个时候天空开始下了倾盆大雨，一共有 $n$ 个雨滴，第 $i(1\leq i\leq n)$ 个雨滴以 $v_gm/s$ 的速度从 $(x_i,y_i)$ 开始匀速下落，同时开始刮起了速度为 $v_wm/s$，方向为 $x$ 轴正方向的大风，可以认为每个雨滴在水平方向上有了和风速一样的速度，以及风不会影响人的行走速度。

Moon 非常喜欢淋雨，为了简单起见把每个雨滴和 Moon 都视为是一个点，只有某 个雨滴到达 $x$ 轴的位置的同时，Moon 也正好在这个位置上，Moon 才可以被这个雨滴淋到。现在给出 $q$ 个询问，第 $i(1\leq i\leq q)$ 次询问给出一个初始位置 $(s_i,0)$，Moon 想知道自己从 $(s_i,0)$ 出发，在整个运动过程中，最多可以被多少个雨滴淋到呢？

$1\leq n,q\leq 105,1\leq v_w,v_g,v_c,y_i\leq 10^6,−10^6\leq x_i,s_i\leq 10^6$。

题解

我们考虑雨滴不动而人去动。可以发现，一个人在 $(x,y)$ 处一秒内能走到的位置是 $(x+v_w-v_c,y+v_g)$ 到 $(x+v_w+v_c,y+v_g)$。那么，我们离线下来每个点，然后从每个 点出发画两条方向为 $(v_w-v_c,v_g)$ 和 $(v_w+v_c,v_g)$ 的射线，这两条射线围起来的面积就 是从这个点出发能够到达的所有点。

由于所有点出发的两条斜线斜率分别相同，所以我们改变坐标系，将这两条斜线当作 $x,y$ 轴，就变为了一个二维偏序问题，离散化后树状数组维护。复杂度 $O((n+q)\log(n+q))$。

T2-验题（verify）

题面

由于原题机爆炸了，小 $S$ 被迫当起了人肉原题机。

小 $S$ 的记忆里有 $n$ 道题，按印象从深到浅依次编号为 $1$ 到 $n$。初始时，有 $m$ 对题 在小 $S$ 思维中存在联系，第 $i$ 对联系连接 $a_i,b_i$。

然而，沿联系 dfs 搜索对小 $S$ 的消耗很大，因此他需要增加一些联系来减少搜索 的深度。具体的，小 $S$ 每次会从一个印象较深的题 $a$，沿联系想到两个印象浅的题 $b,c$（$a<b<c$，$(a,b)$、$(a,c)$ 间有联系，$(b,c)$ 间没有联系），并在 $b,c$ 间添加一对联系。小 $S$ 会不断进行上述操作直到没有联系可以添加。

但过多的联系会使小 $S$ 的大脑爆炸，因此他想知道最终题目间有多少对联系。

$1\leq n\leq 10^5,1\leq a_i<b_i\leq n$。

题解

一个简单的观察是以 $a$ 从小到大的顺序操作能将所有可加的联系都加上，因为操作 $a=i$ 时不会使小于 $i$ 的题增加新联系，进而产生新的 $a<i$ 操作。则有一个暴力的思路是从 $1$ 到 $n$ 枚举 $a$，将所有 $a$ 连向大于 $a$ 的点之间都加上联系，复杂度 $O(n^3)$。

显然两两暴力连接是没前途的。观察操作形式，发现枚举 $a$ 时只要找到 $a$ 连向的点 中最小的 $x$，并只添加 $x$ 与其他 $a$ 连向的点的联系，得到的结果与暴力相同，因为除 $x$ 外的点之间未连接的联系会在 $a=x$ 时进一步连接，直至最终全部被添加。

此时操作相当于将 $a$ 与 $x$ 向编号大的点连出的点集 $\text{merge}$，并计算 $x$ 点集中新增 的点数。使用启发式合并，可以做到 $O(m \log m)$。

T3-颜色（color）

题面

给定一张 $n$ 个点 $m$ 条边的无向简单连通图。

给定正整数 $k$。初始时，每条边的颜色均为蓝色，有一个棋子位于点 $1$，每次操作 你可以把棋子移动到一个相邻的点。

对于每 $k$ 次操作，棋子在这次操作所经过的边会被染成红色。你需要构造一组方 案，使得每条边恰好被染红一次，或者报告无解。

$2\leq n\leq 10^5,n-1\leq m\leq 10^5,1\leq k\leq 10,1\leq u,v\leq n$。

题解

对于 $k=1$ 的情况，就是欧拉路板子。

对于 $k=2$，如果图是一棵树，考虑一个欧拉序，不难发现每条边恰在奇数位置出现一次，偶数位置出现一次，直接输出即可。如果图不是树，可以拉出一个 dfs 树，每走到一个点就把与其相连的返祖边来回走一边。

对于 $k=3$，考虑直接在 $k=2$ 的方案上扩展，例如，如果 $k=2$ 下得到的边的序 列是 $1,2,3,4$，在 $k=3$ 时可以变成 $1,2,2,2,3,4$，变换之后出现在 $3$ 的倍数位置的和边在原序列上出现在偶数位置的边是相同的。

对于 $k>3$，每走一步后随便找一条边来回走即可转化为 $k=2$ 或 $k=3$。

时间复杂度 $O(n)$。

T4-字符串（string）

题面

给出一个长度为 $n$ 的全部由数字组成的字符串 $A$。在此基础上，进行 $Q$ 次询问。

对于第 $i$（$1\leq i\leq Q$）次的询问，给出一个非空字符串 $B^{(i)}$，你需要找出一个最小的 $j$（$0\leq j\leq n$），使得 $A_{1,j}+B^{(i)}+A_{j+1,n}$ 的字典序最小。对于每个询问，你只需要输出你找到的这个 $j$ 即可。

$1\leq n\leq 10^6，1\leq Q\leq 5\times 10^5，1\leq \sum_{i=1}^Q|B^{(i)}| \leq 10^6$。

题解

若 $S+T$ 的字典序小于 $T+S$ 的字典序则称 $S<T$，若 $S+T$ 的字典序小于等于 $T+S$ 的字典序则称 $S\leq T$。

容易注意到如果答案是 $j$ 则 $B\leq A_{j+1,n}$。

而 $\forall 1\leq i\leq j,A_{1,i}<B$。

考虑把 $A$ 划分成 $t$ 个段 $S_1,S_2,\dots,S_T$ 使得 $\forall 1\leq i<t,S_i<S_{i+1}$。

显然有多种划分方式，但是我们取 $|S_i|$ 组成的序列字典序最小的。

易证对于查询串 $B$ 一定只会在 $S_k$ 与 $S_{K+1}$ 之间插入而不会在 $S_k$ 内部插入。

二分出在哪一段插入，用哈希加二分判 $B<S_k$ 是否为真即可。

时间复杂度 $O (q \log n \log (n+m))$。

注：发明出倍增排序查询串并使用双指针可以做到 $O(n \log (n+m)+q \log (n+m))$。